package lib

import "sort"

func init() {
	Probs = append(Probs, Problem{
		Num:         830.3,
		Discription: "博览会",
		Level:       2,
		Labels: map[string]int{
			"多元排序": 1,
			"贪心":   1,
		},
	})
}

// MaxAttendNum 给出一组博览会的开始和结束日期，同一天最多参加k个博览会，最多能参加几个博览会
//  @param intervals 
//  @param k 
//  @return int 
func MaxAttendNum(intervals [][]int, k int) int {
	sort.Slice(intervals, func(i, j int) bool {
		if intervals[i][0] < intervals[j][0] {
			return true
		}

		if intervals[i][0] == intervals[j][0] && intervals[i][1] < intervals[j][1] {
			return true
		}

		return false
	})

	day := intervals[0][0]
	res := 0
	i := 0
	for day <= intervals[len(intervals)-1][1] && i < len(intervals) {
		//跳到有博览会的那天
		if day < intervals[i][0] {
			day = intervals[i][0]
		}

		countByDay := 0
		//在第day天最多能参加几场博览会（开始和结束日期构成的区间包含day的博览会数量，上限为k）
		for i < len(intervals) && countByDay < k && intervals[i][0] <= day && day <= intervals[i][1] {
			i++
			countByDay++
		}

		res += countByDay
		//达到当天参会上限或当天没有更多的博览会后，去下一天
		day++
		//如果日期没结束就把所有会都参加完了，直接退出
		if res == len(intervals) {
			break
		}
	}

	return res
}
